#include <iostream>
// using namespace std;

/**
 * 对arr[l...r]部分进行partition操作
 * 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
 * 记录数组左边界点l,值为v, 右边分成两部分,分界点为j,当前访问元素索引为i,值为e
 * arr[l+1...j) < v  arr[j+1...i-1] > v
 * e > v, i++; e < v, e 和 j+1交换,j++
 * 最后将 l 和 j交换位置
 */
template<typename T>
int __partition(T arr[], int l, int r){
	// 随机选择一个索引
	swap(arr[l], arr[rand()%(r-l+1)+l]);

	T v = arr[l];
	
	// arr[l+1...j] < v; arr[j+1...i) > v
	int j = l;
	for(int i = l + 1;i <= r; ++i){
		if(arr[i] < v){
			swap(arr[j + 1], arr[i]);	// swap(arr[++j], arr[i]);
			j++;
		}
	}
	swap(arr[l], arr[j]);
	return j;
}

// 解决了 含有大量重复元素 退化成O(n^2)
template<typename T>
int __partition2(T arr[], int l, int r){
	// 随机选择一个索引
	swap(arr[l], arr[rand()%(r-l+1)+l]);

	T v = arr[l];
	
	// arr[l+1...i] <= v; arr[j...r) >= v
	int i = l + 1, j = r;
	while(true){
		while(i <= r && arr[i] < v){
			i++;
		}

		while(j >= l + 1 && arr[j] > v){
			j--;
		}
		if(i > j){
			break;
		}

		swap(arr[i], arr[j]);
		i++;
		j--;
	}

	swap(arr[l], arr[j]);

	return j;
}

// arr[l...r] quick sort
template<typename T>
void __quickSort(T arr[], int l, int r){
	if(l >= r){
		return;
	}
	int p = __partition2(arr, l, r);
	__quickSort(arr, l, p - 1);
	__quickSort(arr, p + 1, r);
}

template<typename T>
void quickSort(T arr[], int n){
	srand(time(NULL));
	__quickSort(arr, 0 ,n - 1);
}
